|
In graph theory, the Erdős–Faber–Lovász conjecture is an unsolved problem about graph coloring, named after Paul Erdős, Vance Faber, and László Lovász, who formulated it in 1972.〔.〕 It says: :If complete graphs, each having exactly vertices, have the property that every pair of complete graphs has at most one shared vertex, then the union of the graphs can be colored with colors. ==Equivalent formulations== introduced the problem with a story about seating assignment in committees: suppose that, in a university department, there are committees, each consisting of faculty members, and that all committees meet in the same room, which has chairs. Suppose also that at most one person belongs to the intersection of any two committees. Is it possible to assign the committee members to chairs in such a way that each member sits in the same chair for all the different committees to which he or she belongs? In this model of the problem, the faculty members correspond to graph vertices, committees correspond to complete graphs, and chairs correspond to vertex colors. A ''linear hypergraph'' (also known as partial linear space) is a hypergraph with the property that every two hyperedges have at most one vertex in common. A hypergraph is said to be uniform if all of its hyperedges have the same number of vertices as each other. The cliques of size in the Erdős–Faber–Lovász conjecture may be interpreted as the hyperedges of an -uniform linear hypergraph that has the same vertices as the underlying graph. In this language, the Erdős–Faber–Lovász conjecture states that, given any -uniform linear hypergraph with hyperedges, one may -color the vertices such that each hyperedge has one vertex of each color.〔.〕 A ''simple hypergraph'' is a hypergraph in which at most one hyperedge connects any pair of vertices and there are no hyperedges of size at most one. In the graph coloring formulation of the Erdős–Faber–Lovász conjecture, it is safe to remove vertices that belong to a single clique, as their coloring presents no difficulty; once this is done, the hypergraph that has a vertex for each clique, and a hyperedge for each graph vertex, forms a simple hypergraph. And, the hypergraph dual of vertex coloring is edge coloring. Thus, the Erdős–Faber–Lovász conjecture is equivalent to the statement that any simple hypergraph with vertices has chromatic index (edge coloring number) at most .〔. describes an equivalent problem in the language of set systems instead of hypergraphs.〕 The graph of the Erdős–Faber–Lovász conjecture may be represented as an intersection graph of sets: to each vertex of the graph, correspond the set of the cliques containing that vertex, and connect any two vertices by an edge whenever their corresponding sets have a nonempty intersection. Using this description of the graph, the conjecture may be restated as follows: if some family of sets has total elements, and any two sets intersect in at most one element, then the intersection graph of the sets may be -colored.〔.〕 The intersection number of a graph is the minimum number of elements in a family of sets whose intersection graph is , or equivalently the minimum number of vertices in a hypergraph whose line graph is . define the linear intersection number of a graph, similarly, to be the minimum number of vertices in a linear hypergraph whose line graph is . As they observe, the Erdős–Faber–Lovász conjecture is equivalent to the statement that the chromatic number of any graph is at most equal to its linear intersection number. present another yet equivalent formulation, in terms of the theory of clones. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Erdős–Faber–Lovász conjecture」の詳細全文を読む スポンサード リンク
|